package com.study.lu.链表;

import com.study.lu.链表.bean.Node;

public class 两链表相交 {
    /**
     * 给定两个单向链表，判断这两个链表是否相交,如果相交给出头节点
     * <p/>
     * 链表1:1->2->3->4->5->4
     * 链表2：10->9->8->7->6->5->4
     * 则说明两个链表相交
     *
     * @param args
     */
    public static void main(String[] args) {
        Node node1 = new Node(1,new Node(2,new Node(3,new Node(4,new Node(5,new Node(4,new Node(15)))))));
        Node node2 = new Node(10,new Node(9,new Node(8,new Node(7,new Node(6,new Node(5,new Node(4,new Node(15))))))));
        Node node = 双8快慢循环法(node1, node2);
        System.out.println(null == node ? null : node.data);

    }

    /**
     * 定义两个指针 一个P1从a链表头出发，一个P2从b链表头出发，终会两个链表交点处相遇。
     * P1到头指向链表B的头
     * P2到头指向链表A的头
     * 这样就构成一个P1+P2的环。P1。P2就相当于快慢指针。终止条件是P1==P2
     *
     * @param headA
     * @param headb
     * @return
     */
    private static Node 双8快慢循环法(Node headA, Node headb) {
        Node p1 = headA;
        Node p2 = headb;
        while (p1 != p2) {
            if(p1==null){
                p1=headb;
            }else {
                p1=p1.next;
            }

            if(p2==null){
                p2=headA;
            }else {
                p2=p2.next;
            }
            Object p1o = null == p1 ? null : p1.data;
            Object p2o = null == p2 ? null : p2.data;
            System.out.println("p1="+ p1o+" ,p2o="+p2o);
        }

        return p1;
    }
}
